home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / prio.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.5 KB  |  78 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  prio.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef PRIOH
  19. #define PRIOH
  20.  
  21. //------------------------------------------------------------------------------
  22. // priority queues implemented by fibonacci heaps 
  23. //
  24. // Stefan Naeher  (1989)
  25. //------------------------------------------------------------------------------
  26.  
  27. #include <LEDA/basic.h>
  28.  
  29. #ifndef FHEAPH
  30. #include <LEDA/f_heap.h>
  31. #endif
  32.  
  33. typedef f_heap_item pq_item;
  34.  
  35. #define priority_queue(ktype,itype) name3(itype,ktype,priority_queue)
  36.  
  37.  
  38. #define priority_queuedeclare2(ktype,itype)\
  39. \
  40. struct priority_queue(ktype,itype)  : public f_heap \
  41. {\
  42.   int  cmp(ent& x, ent& y) const { return compare(*(itype*)&(x),*(itype*)&y); }\
  43.   void print_key(ent& x)   const { Print(*(itype*)&x); }\
  44.   void print_inf(ent& x)   const { Print(*(ktype*)&x); }\
  45.   void clear_key(ent& x)   const { Clear(*(itype*)&x); }\
  46.   void clear_inf(ent& x)   const { Clear(*(ktype*)&x); }\
  47.   void copy_key(ent& x)    const { Copy(*(itype*)&x); }\
  48.   void copy_inf(ent& x)    const { Copy(*(ktype*)&x); }\
  49. \
  50.   pq_item insert(ktype k,itype i) { return f_heap::insert(Ent(i),Ent(k));}\
  51. \
  52.   void  del_min(ktype& k, itype& i)   { k = key(find_min());\
  53.                                         i = inf(find_min());\
  54.                                         f_heap::del_min(); }\
  55. \
  56.   ktype del_min()   { ktype x = key(find_min()); f_heap::del_min(); return x; }\
  57.   ktype delete_min(){ ktype x = key(find_min()); f_heap::del_min(); return x; }\
  58.   ktype key(pq_item x)      const { return ktype(f_heap::inf(x)); }\
  59.   itype inf(pq_item x)      const { return itype(f_heap::key(x)); }\
  60.   itype info(pq_item x)     const { return itype(f_heap::key(x)); }\
  61.   void  change_key(pq_item x, ktype k) { f_heap::change_inf(x,Ent(k)); }\
  62.   void  decrease_inf(pq_item x,itype i){ f_heap::decrease_key(x,Ent(i)); }\
  63. \
  64.   priority_queue(ktype,itype)()  {}\
  65.   priority_queue(ktype,itype)(const priority_queue(ktype,itype)& Q)\
  66.   : f_heap((f_heap&)Q)  {}\
  67. \
  68.   priority_queue(ktype,itype)& operator=(const priority_queue(ktype,itype)& Q)\
  69.   { f_heap::operator=((f_heap&)Q); return *this; }\
  70. \
  71.  ~priority_queue(ktype,itype)()  { clear(); }\
  72.  };
  73.  
  74. #define forall_pq_items(i,Q) for(i = (Q).first_item(); i; i=(Q).next_item(i))
  75.  
  76. #endif
  77.  
  78.